﻿using Wintellect.PowerCollections;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace MSFraudExecDep {
    /// <summary>
    /// "Task" artifact definition.
    /// </summary>
    public interface ITask {
        /// <summary>
        /// ID of this task, 
        /// <br/><b>Contract:</b>The ID must be unique in a certain context such as list 
        /// of tasks considered for a batch execution with dependency.
        /// </summary>
        int ID { get; set; } 

        /// <summary>
        /// ID’s of tasks that must run before this tasks.
        /// </summary>
        int[] DependsOn { get; set; }
    }

    /// <summary>
    /// Minimalistic implementation of a Task artifact.
    /// </summary>
    public class TaskBase : ITask {
        private int m_id;

        private int[] m_dependsOn;

        /// <summary>
        /// Constructor without dependencies, with ID only. This constructor initializes the DependsOn field to an empty array
        /// to simplify null handling.
        /// </summary>
        /// <param name="Id">The ID for the given task, see the interface definition for the related contract.</param>
        /// <seealso cref="ITask"/>
        public TaskBase(int Id) {
            m_id = Id;
            m_dependsOn = new int[0];
        }

        /// <summary>
        /// Constructor with the task ID and a list of dependencies; delegates the id-only functionality to the constructor
        /// with the sole parameter of an ID.
        /// </summary>
        /// <param name="Id">The task ID. See the interface definition for the related contract</param>
        /// <param name="DependsOn">Tasks that must run before this task.</param>
        /// <seealso cref="ITask"/>
        public TaskBase(int Id, int[] DependsOn): this(Id) {
            m_dependsOn = DependsOn;
        }

        /// <summary>
        /// The ID of the task, see the interface ITask for more details.
        /// </summary>
        /// <seealso cref="ITask"/>
        public int ID {
            get {
                return m_id;
            }
            set {
                m_id = value;
            }
        }
        /// <summary>
        /// Tasks that must run before this task, see the interface ITask for more details.
        /// </summary>
        /// Ideally, this should be a more durable data structure than an array and it should be read only,
        /// Implemented as stated in the requirements.
        /// <seealso cref="ITask"/>
        public int[] DependsOn {
            get {
                return m_dependsOn;
            }
            set {
                m_dependsOn = value;
            }
        }

        /// <summary>
        /// Provides the task ID and the IDs of all dependent tasks in a compact form.
        /// </summary>
        /// <returns>Compact printable/viwable presentation of the task with task ID and the list of dependencies.</returns>
        public override string ToString() {
            return String.Format("#{1:d}:{0}",
                (m_dependsOn == null ? "none" : string.Join(", "
                    , Array.ConvertAll<int, string>(m_dependsOn, new Converter<int, string>((int i) => i.ToString())))
                ), this.m_id);
        }
    }

    /// <summary>
    /// A List extension with logic of verifying some aspects of validity of a set of tasks, see documentation to the method <tt>assertContent</tt> 
    /// </summary>
    public class TaskList : List<ITask> {

        /// <summary>
        /// Constructor with initial capacity a la the base. Delegates straight to the base.
        /// </summary>
        /// <param name="capacity">Initial capacity of the list</param>
        public TaskList(int capacity) : base(capacity) { }

        /// <summary>
        /// Default constructor with default capacity.
        /// </summary>
        public TaskList() : base() { }

        /// <summary>
        /// Performs smell check on <b>this</b> list of tasks, namely:
        /// <ul>
        /// <li>The list must be not empty, there should be at least one task</li>
        /// <li>If there are duplicate task IDs,</li>
        /// <li>If any of the task IDs referenced by the dep list contain undefined task IDs,</li>
        /// <li>If the dependency list has been forced to null.</li>
        /// </ul>
        /// If this method detects any of the conditions above, it throws a <tt>TaskDependencyException</tt>. 
        /// </summary>
        /// <exception cref="TaskDependencyException">If the smell check fails by one of the conditions above.</exception>
        public void assertContent() {
            Set<int> allIDs = new Set<int>();
            if (Count < 1) {
                throw new TaskDependencyException("Empty task list");
            }
            foreach (ITask task in this) { // individual task quality: duplicate ID detection loop and no null dep (we use empty array instead)
                if (task.DependsOn == null) {
                    throw new TaskDependencyException("Null dependency list forced on the task id " + task.ID);
                }
                if (allIDs.Contains(task.ID)) {
                    throw new TaskDependencyException("Duplicate task id: " + task.ID);
                }
                allIDs.Add(task.ID);
            }
            foreach (ITask task in this) { // undefined ID detection loop
                foreach (int id in task.DependsOn) {
                    if (!allIDs.Contains(id)) {
                        throw new TaskDependencyException(String.Format("The dependency task id {0} of the task {1} is undefined", id, task));
                    }
                }
            }
        }
    }

    /// <summary>
    /// Interface defining arbitrary transform of a list.
    /// </summary>
    /// <typeparam name="T">The type of the list element for transofrmation.</typeparam>
    public interface IListTransformer<T> {

        /// <summary>
        /// Arbitrary transformation operation, projecting the source by some rules into return result.
        /// </summary>
        /// <param name="source">The original list of items to be transformed.</param>
        /// <returns>Result of the transformation.</returns>
        IList<T> Transform(IList<T> source);
    }

    /// <summary>
    /// Task dependency related exception.
    /// </summary>
    public class TaskDependencyException : Exception {
        /// <summary>
        /// Constructor with the message alone; delegates to the base.
        /// </summary>
        /// <param name="message">The error message delegated to the base constructor.</param>
        public TaskDependencyException(string message) : base(message) { }
        /// <summary>
        /// Constructor with the message and the last known root cause fo the problem. Delegates straight
        /// to the base.
        /// </summary>
        /// <param name="message">The error message delegated to the base constructor.</param>
        /// <param name="cause">The root cause exception delegated to the base constructor.</param>
        public TaskDependencyException(string message, Exception cause): base(message, cause) {}
    }

    /// <summary>
    /// <para>Implementation of the list transformer applied to the problem of ordering instances of ITask in the order
    /// of execution per specified dependencies. If the dependency graph is not connected, there is no guarantee 
    /// of order of fully conntected subgraphs which should not mean any trouble if the tasks in distinct subgraphs
    /// are considered unrelated. </para>
    /// That is, the code assumes that <b>all</b> tasks defined must be executed in order, not only one of the connected graphs
    /// in which case the API should include target task for which the connected subgraph should be lined up for execution.
    /// <b>Contract:</b>
    /// <ul>
    /// <li>The list must have at least one task.</li>
    /// <li>There can be no duplicate task IDs.</li>
    /// <li>There should be no cyclic dependencies, a cyclic dependency will be detected and cause an error.</li>
    /// <li>Depencencies must reference a defined task.</li>
    /// </ul>
    /// </summary>
    public class TaskDependencyOrderer : IListTransformer<ITask> {

        /// <summary>
        /// Delegates to the Transform method acting as a bridge. This method name and signature has been specified in the requirements.
        /// It is completely interchangeable with the Transform method.
        /// </summary>
        /// <param name="tasks">Original, possibly unordered task list.</param>
        /// <returns>The ordered task list in the order of execution</returns>
        public IList<ITask> GetExecutionOrder(IList<ITask> tasks) {
            return Transform(tasks);
        }

        /// <summary>
        /// Builds a dictionary keyed by a task id to the task. 
        /// </summary>
        /// <param name="tasks">A list of task that is expected to be unordered.</param>
        /// <returns>A dictionary keyed by a task ID pointing to the instance of the related task.</returns>
        /// <exception cref="TaskDependencyException">Thrown if:
        /// <ul>
        /// <li>A duplicate ID is detected</li>
        /// </ul>
        /// </exception>
        public static Dictionary<int, ITask> BuildAllTasksDictionary(IList<ITask> tasks) {
            Dictionary<int, ITask> result = new Dictionary<int, ITask>();
            foreach (ITask task in tasks) {
                if (result.ContainsKey(task.ID)) {
                    throw new TaskDependencyException("Duplicate task id: " + task.ID);
                }
                result.Add(task.ID, task);
            }
            return result;
        }
        
        /// <summary>
        /// Node visitation state.
        /// </summary>
        private enum VisitState { None, Visiting, Done};

        /// <summary>
        /// Orders the tasks passed in the argument for the "tasks" parameter, returns the list of the tasks in the order of execution.
        /// Applies topological sort to the dependency graph.
        /// </summary>
        /// <param name="tasks">The list of the tasks to line up for execution order per the dependencies on each.</param>
        /// <returns>The list of tasks passed in the argument to the parameter tasks, in execution order per depencencies specified on each.</returns>
        /// <exception cref="TaskDependencyException">Thrown if:
        /// <ul>
        /// <li>If the task list is found empty (less than one task)</li>
        /// <li>Programming error: a task ID found missing from the task dictionary built by this method.</li>
        /// </ul>
        /// </exception>
        /// <seealso cref="ITask"/>
        /// <seealso cref="TaskBase"/>
        public IList<ITask> Transform(IList<ITask> tasks) {
            // ideally, I would use a TaskList type as a parameter, but following the specifications here.
            if (tasks.Count < 1) {
                throw new TaskDependencyException("Empty task list");
            }
            Dictionary<int, ITask> allTasks = BuildAllTasksDictionary(tasks);
            IList<int> execOrder = Sort(tasks, allTasks);
            IList<ITask> result = new List<ITask>(execOrder.Count);
            foreach (int id in execOrder) {
                ITask task = null;
                if(!allTasks.TryGetValue(id, out task)) {
                    throw new TaskDependencyException("After visiting, task ID missing in the dictionary: " + id);
                }
                result.Add(task);
            }
            return result;
        }

        /// <summary>
        /// Runs topological sort on the given task collection with the helper dictionary.
        /// </summary>
        /// <param name="tasks">Tasks that need to be ordered.</param>
        /// <param name="allTasks">All task dictionary keyed by a task ID.</param>
        /// <returns>Tasks in the order of execution per dependencies</returns>
        /// <exception cref="TaskDependencyException">Thrown if:
        /// <ul>
        /// <li>Programming (algorithmic) error is detected.</li>
        /// </ul>
        /// </exception>
        private IList<int> Sort(IList<ITask> tasks, Dictionary<int, ITask> allTasks) {
            int allTaskCount = allTasks.Keys.Count;
            Dictionary<int, VisitState> visitStates = new Dictionary<int, VisitState>(allTaskCount * 2);
            Deque<int> execOrder = new Deque<int>();
            Deque<int> visitTrack = new Deque<int>();

            // visitations to build dependency line up, DFS
            foreach (ITask task in tasks) {
                VisitState state = VisitState.None;
                visitStates.TryGetValue(task.ID, out state);
                if (state == VisitState.None) {
                    VisitOne(task.ID, visitStates, allTasks, visitTrack, execOrder);
                }
                else if (state == VisitState.Visiting) {
                    throw new TaskDependencyException(String.Format("Task id={0} found in visiting state; means algorithm error", task.ID));
                }
                // for the state Done, nothing to do.
            }
            return execOrder;
        }

        /// <summary>
        /// Starting from the given graph node (in this case a task), visits related nodes, putting together execution order.
        /// If it finds a node in "Visiting" state, which means a cyclic dependency, throws an exception.
        /// </summary>
        /// <exception cref="TaskDependencyException">
        /// The method throws this exception in one of the two cases:
        /// <ul>
        /// <li><b>A cycle is detected</b> - in this case the Exception message includes the suspected path where curcular dependency was be found.</li>
        /// <li><b>Undefined node id (i.e. task ID)</b></li>
        /// </ul>
        /// </exception>
        private void VisitOne(int visitedId, Dictionary<int, VisitState> visitStates, Dictionary<int, ITask> allTasks
                 , Deque<int> visitTrack, Deque<int> execOrderList) {
            visitStates[visitedId] = VisitState.Visiting; 
            visitTrack.AddToFront(visitedId);
            ITask task = null;
            allTasks.TryGetValue(visitedId, out task);
            if(task == null) { // the task is not defined
                throw new TaskDependencyException( String.Format("Target {0} referenced by target: {0} is undefined",
                      visitedId, (visitTrack.Count > 0 ? visitTrack.GetAtFront().ToString() : "none")
                    ));
            }
            for(int depIndex = 0; depIndex < task.DependsOn.Length; depIndex++) {
                int depId = task.DependsOn[depIndex];
                VisitState depState = VisitState.None;
                visitStates.TryGetValue(depId, out depState);
                if(depState == VisitState.Visiting){
                    throw getCycleDetectedException(depId, visitTrack);
                }
                if(depState != VisitState.Done) {
                    VisitOne(depId, visitStates, allTasks, visitTrack, execOrderList);
                }
            }
            int lastId = visitTrack.RemoveFromFront();
            if (visitedId != lastId) {
                throw new TaskDependencyException(String.Format("Backtracking error: expected node {0}, received {0} instead", visitedId, lastId));
            }
            visitStates[visitedId] = VisitState.Done;
            execOrderList.Add(visitedId);
        }

        /// <summary>
        /// Puts together an Exception with the error message including path with detected cyclic dependency and throws the exception.
        /// </summary>
        /// <param name="taskID">The task that has triggered cyclic dependency</param>
        /// <param name="path">The path for the task</param>
        /// <exception cref="TaskDependencyException">The method throws this exception in the end with the message
        /// that includes a path with circular dependency</exception>
        private TaskDependencyException getCycleDetectedException(int taskID, Deque<int> path) {
            StringBuilder sb = new StringBuilder();
            sb.Append("Circular dependency detected by the task ID=")
                .Append(taskID).Append("; trace:").Append(Environment.NewLine);
            foreach (int id in path) { // this certifiably loops from the front
                sb.Append('\t').Append(id);
            }
            return new TaskDependencyException(sb.ToString());
        }
    }
}
